import java.util.Stack;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-06
 * Time:22:33
 */

/**
 * BM10两个链表的第一个公共结点
 */

public class FindFirstCommonNode {
    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(6);
        headA.next.next.next.next = new ListNode(7);

        ListNode headB = new ListNode(4);
        headB.next = new ListNode(5);
        headB.next.next = new ListNode(6);
        headB.next.next.next = new ListNode(7);

        headB.next.next = headA.next.next.next;

        ListNode commonNode = FindFirstCommonNode(headA, headB);

        if (commonNode != null) {
            System.out.println(commonNode.val); // 输出6
        } else {
            System.out.println("null");
        }

    }
    public static ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
        // 遍历两个链表，求出它们的长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // 如果链表A比链表B长，则先移动链表A的头指针
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }

        // 如果链表B比链表A长，则先移动链表B的头指针
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }

        // 同时移动两个链表的指针，直到找到第一个公共节点
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        // 如果存在公共节点，返回该节点；否则返回null
        return headA;
    }
    // 求链表的长度
    public static int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}
